#!/usr/bin/env python
#encoding: latin1

class DatosPunto2(object):
	""" Clase para guardar los datos de entrada """
	def __init__(self):
		self._cantidad_meses = 0
		self._capacidad_deposito = 0
		self._costo_almacenar = 0
		self._tasa_orden_compra = 0
		self._demanda = []

	@property
	def cantidad_meses(self):
		return self._cantidad_meses

	@cantidad_meses.setter
	def cantidad_meses(self, value):
		self._cantidad_meses = value

	@property
	def capacidad_deposito(self):
		return self._capacidad_deposito

	@capacidad_deposito.setter
	def capacidad_deposito(self, value):
		self._capacidad_deposito = value

	@property
	def costo_almacenar(self):
		return self._costo_almacenar

	@costo_almacenar.setter
	def costo_almacenar(self, value):
		self._costo_almacenar = value

	@property
	def tasa_orden_compra(self):
		return self._tasa_orden_compra

	@tasa_orden_compra.setter
	def tasa_orden_compra(self, value):
		self._tasa_orden_compra = value

	@property
	def demanda(self):
		return self._demanda

	def agregar_demanda(self, value):
		self._demanda.append(value)

class MatrizSolucion(object):
	""" Clase con matrices para almacenar la solución """
	def __init__(self, datos):
		# Matriz que guarda el costo óptimo para un mes y una cantidad de camiones determinada
		self._costo_optimo = [[0 for cantidad_camiones in xrange(datos.capacidad_deposito + 1)] for mes in range(datos.cantidad_meses)]
		# Matriz que guarda la cantida de camiones comprada para un mes y una cantidad de camiones determinada
		self._cantidad_comprada = [[0 for cantidad_camiones in xrange(datos.capacidad_deposito + 1)] for mes in range(datos.cantidad_meses)]
		# Matriz que guarda la posición en la matriz de la solución previa
		self._solucion_previa = [[(0, 0) for cantidad_camiones in xrange(datos.capacidad_deposito + 1)] for mes in range(datos.cantidad_meses)]

	@property
	def costo_optimo(self):
		return self._costo_optimo

	@property
	def cantidad_comprada(self):
		return self._cantidad_comprada

	@property
	def solucion_previa(self):
		return self._solucion_previa


def iniciar_programa():
	print "TP2 de Teoría de Algoritmos. Punto 2: Problema del inventario"
	while True:
		try:
			archivo = raw_input("Nombre del archivo a procesar: ")
			break
		except IOError:
			print "El archivo es inválido."
	return archivo


def leer_archivo(nombre_archivo):
	archivo = open(nombre_archivo)
	datos = DatosPunto2()

	try:
		datos.cantidad_meses = int(archivo.readline())
		datos.capacidad_deposito = int(archivo.readline())
		datos.costo_almacenar = int(archivo.readline())
		datos.tasa_orden_compra = int(archivo.readline())

		espacio_blanco = archivo.readline()

		for i in xrange(datos.cantidad_meses):
			linea = archivo.readline().rstrip('\n')
			datos.agregar_demanda(int(linea))	

	except (IOError, ValueError):
		print "El archivo es inválido"
		datos = None

	archivo.close()

	return datos

def armar_matriz(datos):
	# Creación de la matriz
	matriz = MatrizSolucion(datos)

	for cantidad_camiones in xrange(datos.capacidad_deposito + 1):
		# Para el mes 0, el costo óptimo es igual a la emisión de la orden de compra si la demanda es mayor a cero
		matriz.costo_optimo[0][cantidad_camiones] = datos.tasa_orden_compra if cantidad_camiones > 0 or datos.demanda[0] > 0 else 0
		# Para el mes 0 siempre se compra toda la demanda del mes
		matriz.cantidad_comprada[0][cantidad_camiones] = cantidad_camiones + datos.demanda[0]
		matriz.solucion_previa[0][cantidad_camiones] = None
	
	for mes in xrange(1, datos.cantidad_meses):
		for cantidad_camiones in xrange(datos.capacidad_deposito + 1):
			if datos.demanda[mes] + cantidad_camiones <= datos.capacidad_deposito:
				
				# Si hay capacidad en el depósito, se decide entre comprar todo este mes o en un mes anterior
				costo_comprar_este_mes = datos.tasa_orden_compra + matriz.costo_optimo[mes - 1][0]
				costo_comprar_mes_anterior = (datos.demanda[mes] + cantidad_camiones) * datos.costo_almacenar + matriz.costo_optimo[mes - 1][datos.demanda[mes] + cantidad_camiones]
				
				if costo_comprar_este_mes <= costo_comprar_mes_anterior:
					matriz.costo_optimo[mes][cantidad_camiones] = costo_comprar_este_mes
					matriz.cantidad_comprada[mes][cantidad_camiones] = datos.demanda[mes] + cantidad_camiones
					matriz.solucion_previa[mes][cantidad_camiones] = (mes - 1, 0)
				else:
					matriz.costo_optimo[mes][cantidad_camiones] = costo_comprar_mes_anterior
					matriz.cantidad_comprada[mes][cantidad_camiones] = 0
					matriz.solucion_previa[mes][cantidad_camiones] = (mes - 1, datos.demanda[mes] + cantidad_camiones)

			else:
				# Si no hay capacidad se compra todo este mes
				matriz.costo_optimo[mes][cantidad_camiones] = datos.tasa_orden_compra + matriz.costo_optimo[mes - 1][0]
				matriz.cantidad_comprada[mes][cantidad_camiones] = datos.demanda[mes] + cantidad_camiones
				matriz.solucion_previa[mes][cantidad_camiones] = (mes - 1, 0)

	return matriz
	

def calcular_punto_2(matriz_solucion, datos):
	print "Costo óptimo: " + str(matriz_solucion.costo_optimo[datos.cantidad_meses - 1][0])

	cantidad_comprada = {}
	cantidad_comprada[datos.cantidad_meses] = matriz_solucion.cantidad_comprada[datos.cantidad_meses - 1][0]

	solucion = matriz_solucion.solucion_previa[datos.cantidad_meses - 1][0]
	while (solucion is not None):
		cantidad_comprada[solucion[0] + 1] = matriz_solucion.cantidad_comprada[solucion[0]][solucion[1]]
		solucion = matriz_solucion.solucion_previa[solucion[0]][solucion[1]]

	for mes in xrange(1, datos.cantidad_meses + 1):
		print "El mes " + str(mes) + " se compraron " + str(cantidad_comprada[mes]) + " camiones."

def main():
	nombre_archivo = iniciar_programa()
	datos = leer_archivo(nombre_archivo)

	if datos is not None:
		matriz_solucion = armar_matriz(datos)
		calcular_punto_2(matriz_solucion, datos)


main()

